<!DOCTYPE html>
<html lang="zh-CN">
    <head>
        <meta charset="utf-8">
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <meta name="robots" content="noodp" />
        <title>来自上帝的骰子---Treap(树堆)详解 - L_B__</title><meta name="referrer" content="no-referrer">
<meta name="description" content="来自上帝的骰子---Treap(树堆)详解"><meta property="og:title" content="来自上帝的骰子---Treap(树堆)详解" />
<meta property="og:description" content="来自上帝的骰子---Treap(树堆)详解" />
<meta property="og:type" content="article" />
<meta property="og:url" content="https://acking-you.github.io/posts/%E6%9D%A5%E8%87%AA%E4%B8%8A%E5%B8%9D%E7%9A%84%E9%AA%B0%E5%AD%90-treap%E6%A0%91%E5%A0%86%E8%AF%A6%E8%A7%A3/" /><meta property="og:image" content="https://acking-you.github.io/logo.png"/><meta property="article:section" content="posts" />
<meta property="article:published_time" content="2022-02-16T00:00:00+00:00" />
<meta property="article:modified_time" content="2022-02-16T00:00:00+00:00" />

<meta name="twitter:card" content="summary_large_image"/>
<meta name="twitter:image" content="https://acking-you.github.io/logo.png"/>

<meta name="twitter:title" content="来自上帝的骰子---Treap(树堆)详解"/>
<meta name="twitter:description" content="来自上帝的骰子---Treap(树堆)详解"/>
<meta name="application-name" content="FeelIt">
<meta name="apple-mobile-web-app-title" content="FeelIt"><meta name="theme-color" content="#ffffff"><meta name="msapplication-TileColor" content="#da532c"><link rel="canonical" href="https://acking-you.github.io/posts/%E6%9D%A5%E8%87%AA%E4%B8%8A%E5%B8%9D%E7%9A%84%E9%AA%B0%E5%AD%90-treap%E6%A0%91%E5%A0%86%E8%AF%A6%E8%A7%A3/" /><link rel="prev" href="https://acking-you.github.io/posts/leetcode%E6%83%85%E4%BA%BA%E8%8A%82%E7%89%B9%E8%BE%91%E5%AF%BB%E6%89%BE%E5%8D%95%E8%BA%AB%E7%8B%97/" /><link rel="next" href="https://acking-you.github.io/posts/%E6%96%B0%E6%89%8B%E7%94%A8c&#43;&#43;%E5%86%99%E4%BA%86%E4%B8%AA%E6%B3%9B%E5%9E%8B%E5%A0%86%E6%95%88%E7%8E%87%E7%AB%9F%E6%AF%94stl%E7%9A%84%E6%9B%B4%E5%BF%AB/" /><link rel="stylesheet" href="/css/page.min.css"><link rel="stylesheet" href="/css/home.min.css"><script type="application/ld+json">
    {
        "@context": "http://schema.org",
        "@type": "BlogPosting",
        "headline": "来自上帝的骰子---Treap(树堆)详解",
        "inLanguage": "zh-CN",
        "mainEntityOfPage": {
            "@type": "WebPage",
            "@id": "https:\/\/acking-you.github.io\/posts\/%E6%9D%A5%E8%87%AA%E4%B8%8A%E5%B8%9D%E7%9A%84%E9%AA%B0%E5%AD%90-treap%E6%A0%91%E5%A0%86%E8%AF%A6%E8%A7%A3\/"
        },"genre": "posts","keywords": "来自上帝的骰子---Treap(树堆)详解","wordcount":  3742 ,
        "url": "https:\/\/acking-you.github.io\/posts\/%E6%9D%A5%E8%87%AA%E4%B8%8A%E5%B8%9D%E7%9A%84%E9%AA%B0%E5%AD%90-treap%E6%A0%91%E5%A0%86%E8%AF%A6%E8%A7%A3\/","datePublished": "2022-02-16T00:00:00+00:00","dateModified": "2022-02-16T00:00:00+00:00","publisher": {
            "@type": "Organization",
            "name": "作者"},"author": {
                "@type": "Person",
                "name": "作者"
            },"description": "来自上帝的骰子---Treap(树堆)详解"
    }
    </script></head><body data-header-desktop="auto" data-header-mobile="auto"><script>(window.localStorage && localStorage.getItem('theme') ? localStorage.getItem('theme') === 'dark' : ('auto' === 'auto' ? window.matchMedia('(prefers-color-scheme: dark)').matches : 'auto' === 'dark')) && document.body.setAttribute('theme', 'dark');</script>

        <div id="mask"></div><div class="wrapper"><header class="desktop" id="header-desktop">
    <div class="header-wrapper">
        <div class="header-title">
            <a href="/" title="L_B__">L_B__</a>
        </div>
        <div class="menu">
            <div class="menu-inner"><a class="menu-item" href="/posts/"> 文章 </a><a class="menu-item" href="/tags/"> 标签 </a><a class="menu-item" href="/categories/"> 分类 </a><span class="menu-item delimiter"></span><span class="menu-item search" id="search-desktop">
                        <input type="text" placeholder="搜索文章标题或内容..." id="search-input-desktop">
                        <a href="#" class="search-button search-toggle" id="search-toggle-desktop" title="搜索">
                            <i class="fas fa-search fa-fw"></i>
                        </a>
                        <a href="#" class="search-button search-clear" id="search-clear-desktop" title="清空">
                            <i class="fas fa-times-circle fa-fw"></i>
                        </a>
                        <span class="search-button search-loading" id="search-loading-desktop">
                            <i class="fas fa-spinner fa-fw fa-spin"></i>
                        </span>
                    </span><a href="javascript:void(0);" class="menu-item theme-switch" title="切换主题">
                    <i class="fas fa-adjust fa-fw"></i>
                </a>
            </div>
        </div>
    </div>
</header><header class="mobile" id="header-mobile">
    <div class="header-container">
        <div class="header-wrapper">
            <div class="header-title">
                <a href="/" title="L_B__">L_B__</a>
            </div>
            <div class="menu-toggle" id="menu-toggle-mobile">
                <span></span><span></span><span></span>
            </div>
        </div>
        <div class="menu" id="menu-mobile"><div class="search-wrapper">
                    <div class="search mobile" id="search-mobile">
                        <input type="text" placeholder="搜索文章标题或内容..." id="search-input-mobile">
                        <a href="#" class="search-button search-toggle" id="search-toggle-mobile" title="搜索">
                            <i class="fas fa-search fa-fw"></i>
                        </a>
                        <a href="#" class="search-button search-clear" id="search-clear-mobile" title="清空">
                            <i class="fas fa-times-circle fa-fw"></i>
                        </a>
                        <span class="search-button search-loading" id="search-loading-mobile">
                            <i class="fas fa-spinner fa-fw fa-spin"></i>
                        </span>
                    </div>
                    <a href="#" class="search-cancel" id="search-cancel-mobile">
                        取消
                    </a>
                </div><a class="menu-item" href="/posts/" title="">文章</a><a class="menu-item" href="/tags/" title="">标签</a><a class="menu-item" href="/categories/" title="">分类</a><div class="menu-item"><a href="javascript:void(0);" class="theme-switch" title="切换主题">
                    <i class="fas fa-adjust fa-fw"></i>
                </a>
            </div></div>
    </div>
</header><div class="search-dropdown desktop">
    <div id="search-dropdown-desktop"></div>
</div>
<div class="search-dropdown mobile">
    <div id="search-dropdown-mobile"></div>
</div><main class="main">
                <div class="container"><div class="toc" id="toc-auto">
            <h2 class="toc-title">目录</h2>
            <div class="toc-content" id="toc-content-auto"></div>
        </div><article class="page single" data-toc="disable"><div class="featured-image"><img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/img_convert/30474f138a1fd099890cfcb17099a60b.png#pic_center"
        data-srcset="https://img-blog.csdnimg.cn/img_convert/30474f138a1fd099890cfcb17099a60b.png#pic_center, https://img-blog.csdnimg.cn/img_convert/30474f138a1fd099890cfcb17099a60b.png#pic_center 1.5x, https://img-blog.csdnimg.cn/img_convert/30474f138a1fd099890cfcb17099a60b.png#pic_center 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/img_convert/30474f138a1fd099890cfcb17099a60b.png#pic_center"
        title="来自上帝的骰子---Treap(树堆)详解" /></div><div class="single-card" data-image="true"><h2 class="single-title animated flipInX">来自上帝的骰子---Treap(树堆)详解</h2><div class="post-meta">
                <div class="post-meta-line"><span class="post-author"><a href="/" title="Author" rel=" author" class="author"><i class="fas fa-user-circle fa-fw"></i>作者</a></span>&nbsp;<span class="post-category">出版于  <a href="/categories/%E6%89%8B%E5%86%99%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/"><i class="far fa-folder fa-fw"></i>手写数据结构</a></span></div>
                <div class="post-meta-line"><span><i class="far fa-calendar-alt fa-fw"></i>&nbsp;<time datetime="2022-02-16">2022-02-16</time></span>&nbsp;<span><i class="fas fa-pencil-alt fa-fw"></i>&nbsp;约 3742 字</span>&nbsp;
                    <span><i class="far fa-clock fa-fw"></i>&nbsp;预计阅读 8 分钟</span>&nbsp;</div>
            </div>
            
            <hr><div class="details toc" id="toc-static"  data-kept="">
                    <div class="details-summary toc-title">
                        <span>目录</span>
                        <span><i class="details-icon fas fa-angle-right"></i></span>
                    </div>
                    <div class="details-content toc-content" id="toc-content-static"><nav id="TableOfContents">
  <ul>
    <li><a href="#为什么说是上帝的骰子">为什么说是上帝的骰子？</a></li>
    <li><a href="#treap实现">Treap实现</a>
      <ul>
        <li><a href="#1-结点的结构">1. 结点的结构</a></li>
        <li><a href="#2-treap的抽象数据结构">2. Treap的抽象数据结构</a></li>
        <li><a href="#3-左旋和右旋">3. 左旋和右旋</a></li>
        <li><a href="#4-插入和删除">4. 插入和删除</a></li>
        <li><a href="#5-查询排名">5. 查询排名</a></li>
        <li><a href="#6-按排名查询值">6. 按排名查询值</a></li>
        <li><a href="#7-查询前驱后继">7. 查询前驱后继</a></li>
        <li><a href="#8-销毁treap">8. 销毁Treap</a></li>
        <li><a href="#9-迭代器的设计">9. 迭代器的设计</a></li>
      </ul>
    </li>
    <li><a href="#完整源代码">完整源代码</a>
      <ul>
        <li><a href="#treaph">Treap.h</a></li>
        <li><a href="#treapcpp">Treap.cpp</a></li>
      </ul>
    </li>
    <li><a href="#测试">测试</a>
      <ul>
        <li><a href="#avl-vs-treap-vs-普通bst">AVL vs Treap vs 普通BST</a></li>
      </ul>
    </li>
  </ul>
</nav></div>
                </div><div class="content" id="content"><h2 id="为什么说是上帝的骰子">为什么说是上帝的骰子？</h2>
<p>解释这个问题，首先由这个数据结构的名字开始，Treap = Tree + Heap，即为树堆之意，然而实际上用到堆的地方就是<strong>利用了一个随机的值标记每个结点，然后根据这个值对树进行左旋、右旋操作来调整父子树直接的关系</strong>，你可以严格让它遵循小根堆也可以遵循大根堆，这都无所谓。</p>
<p>也就是说每个结点的结构需要额外存储一个随机值，来决定它是否旋转调整，这对比普通的BST就要优越很多了，但这个也看运气，如果骰子没摇好，出现极端的情况，则可能即便是旋转了多次还是效率低下，我后面对BST、Treap、AVL进行了各方面的对比。</p>
<p><strong>相对AVL，它不需要记录深度，不需要根据深度来判断是否旋转，旋转这件事就完全交给老天了，而且也不存在复杂的旋转情况，只有左旋和右旋。</strong></p>
<p>注意：我写的这个Treap是以大根堆的方式进行维护的！也就是父节点大于子节点的随机值。</p>
<h2 id="treap实现">Treap实现</h2>
<h3 id="1-结点的结构">1. 结点的结构</h3>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">struct</span> <span class="nc">node</span> <span class="p">{</span>
	<span class="c1">//值、优先级(随机数、该数的总结点数、该结点的val次数
</span><span class="c1"></span>    <span class="kt">int</span> <span class="n">val</span><span class="p">,</span> <span class="n">priority</span><span class="p">,</span> <span class="n">length</span><span class="p">,</span> <span class="n">cnt</span><span class="p">;</span>
    <span class="n">node</span> <span class="o">*</span><span class="n">lchild</span><span class="p">;</span>
    <span class="n">node</span> <span class="o">*</span><span class="n">rchild</span><span class="p">;</span>

    <span class="n">node</span><span class="p">()</span> <span class="o">:</span> <span class="n">val</span><span class="p">(</span><span class="mi">0</span><span class="p">),</span> <span class="n">length</span><span class="p">(</span><span class="mi">1</span><span class="p">),</span> <span class="n">cnt</span><span class="p">(</span><span class="mi">1</span><span class="p">),</span> <span class="n">lchild</span><span class="p">(</span><span class="k">nullptr</span><span class="p">),</span> <span class="n">rchild</span><span class="p">(</span><span class="k">nullptr</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">srand</span><span class="p">((</span><span class="kt">unsigned</span><span class="p">)</span> <span class="n">time</span><span class="p">(</span><span class="nb">NULL</span><span class="p">));</span><span class="c1">//记得重新设定种子
</span><span class="c1"></span>        <span class="n">priority</span> <span class="o">=</span> <span class="n">rand</span><span class="p">();</span>
    <span class="p">}</span>

    <span class="n">node</span><span class="p">(</span><span class="kt">int</span> <span class="n">val</span><span class="p">)</span> <span class="o">:</span> <span class="n">val</span><span class="p">(</span><span class="n">val</span><span class="p">),</span> <span class="n">length</span><span class="p">(</span><span class="mi">1</span><span class="p">),</span> <span class="n">cnt</span><span class="p">(</span><span class="mi">1</span><span class="p">),</span> <span class="n">lchild</span><span class="p">(</span><span class="k">nullptr</span><span class="p">),</span> <span class="n">rchild</span><span class="p">(</span><span class="k">nullptr</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">srand</span><span class="p">((</span><span class="kt">unsigned</span><span class="p">)</span> <span class="n">time</span><span class="p">(</span><span class="nb">NULL</span><span class="p">));</span>
        <span class="n">priority</span> <span class="o">=</span> <span class="n">rand</span><span class="p">();</span>
    <span class="p">}</span>

    <span class="kt">void</span> <span class="nf">update</span><span class="p">()</span> <span class="p">{</span>
        <span class="n">length</span> <span class="o">=</span> <span class="n">cnt</span><span class="p">;</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">lchild</span> <span class="o">!=</span> <span class="k">nullptr</span><span class="p">)</span><span class="n">length</span> <span class="o">+=</span> <span class="n">lchild</span><span class="o">-&gt;</span><span class="n">length</span><span class="p">;</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">rchild</span> <span class="o">!=</span> <span class="k">nullptr</span><span class="p">)</span><span class="n">length</span> <span class="o">+=</span> <span class="n">rchild</span><span class="o">-&gt;</span><span class="n">length</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">};</span>
</code></pre></div><h3 id="2-treap的抽象数据结构">2. Treap的抽象数据结构</h3>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">class</span> <span class="nc">Treap</span> <span class="p">{</span>
    <span class="n">node</span> <span class="o">*</span><span class="n">head</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">length</span><span class="p">;</span>
<span class="k">public</span><span class="o">:</span>
    <span class="cm">/*construct&amp;destruct*/</span>
    <span class="n">Treap</span><span class="p">()</span> <span class="o">:</span> <span class="n">head</span><span class="p">(</span><span class="k">nullptr</span><span class="p">),</span> <span class="n">length</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span> <span class="p">{}</span>

    <span class="n">Treap</span><span class="p">(</span><span class="kt">int</span> <span class="n">val</span><span class="p">)</span> <span class="o">:</span> <span class="n">head</span><span class="p">(</span><span class="k">new</span> <span class="n">node</span><span class="p">(</span><span class="n">val</span><span class="p">)),</span> <span class="n">length</span><span class="p">(</span><span class="mi">1</span><span class="p">)</span> <span class="p">{}</span>

<span class="k">public</span><span class="o">:</span><span class="c1">//内部类设计迭代器
</span><span class="c1"></span>    <span class="k">class</span> <span class="nc">iterator</span> <span class="p">{</span>
        <span class="n">node</span> <span class="o">*</span><span class="n">head</span><span class="p">;</span>
        <span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">;</span>
    <span class="k">public</span><span class="o">:</span>
        <span class="cm">/*迭代器部分*/</span>
        <span class="n">iterator</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">head</span><span class="p">,</span> <span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="o">:</span> <span class="n">head</span><span class="p">(</span><span class="n">head</span><span class="p">),</span> <span class="n">root</span><span class="p">(</span><span class="n">root</span><span class="p">)</span> <span class="p">{}</span>

        <span class="n">iterator</span> <span class="o">&amp;</span><span class="k">operator</span><span class="o">++</span><span class="p">()</span> <span class="p">{</span>
            <span class="n">root</span> <span class="o">=</span> <span class="n">queryNext</span><span class="p">(</span><span class="n">head</span><span class="p">,</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">);</span>
            <span class="k">return</span> <span class="o">*</span><span class="k">this</span><span class="p">;</span>
        <span class="p">}</span>

        <span class="n">iterator</span> <span class="k">operator</span><span class="o">++</span><span class="p">(</span><span class="kt">int</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">iterator</span> <span class="n">t</span> <span class="o">=</span> <span class="o">*</span><span class="k">this</span><span class="p">;</span>
            <span class="n">root</span> <span class="o">=</span> <span class="n">queryNext</span><span class="p">(</span><span class="n">head</span><span class="p">,</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">);</span>
            <span class="k">return</span> <span class="n">t</span><span class="p">;</span>
        <span class="p">}</span>

        <span class="n">iterator</span> <span class="o">&amp;</span><span class="k">operator</span><span class="o">--</span><span class="p">()</span> <span class="p">{</span>
            <span class="n">root</span> <span class="o">=</span> <span class="n">queryPre</span><span class="p">(</span><span class="n">head</span><span class="p">,</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">);</span>
            <span class="k">return</span> <span class="o">*</span><span class="k">this</span><span class="p">;</span>
        <span class="p">}</span>

        <span class="n">iterator</span> <span class="k">operator</span><span class="o">--</span><span class="p">(</span><span class="kt">int</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">iterator</span> <span class="n">t</span> <span class="o">=</span> <span class="o">*</span><span class="k">this</span><span class="p">;</span>
            <span class="n">root</span> <span class="o">=</span> <span class="n">queryPre</span><span class="p">(</span><span class="n">head</span><span class="p">,</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">);</span>
            <span class="k">return</span> <span class="n">t</span><span class="p">;</span>
        <span class="p">}</span>

        <span class="kt">int</span> <span class="k">operator</span><span class="o">*</span><span class="p">()</span> <span class="p">{</span>
            <span class="k">return</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">;</span>
        <span class="p">}</span>

        <span class="kt">bool</span> <span class="k">operator</span><span class="o">!=</span><span class="p">(</span><span class="k">const</span> <span class="n">iterator</span> <span class="o">&amp;</span><span class="n">t</span><span class="p">)</span> <span class="p">{</span>
            <span class="k">return</span> <span class="n">t</span><span class="p">.</span><span class="n">root</span> <span class="o">!=</span> <span class="n">root</span><span class="p">;</span>
        <span class="p">}</span>
    <span class="p">};</span>

<span class="k">private</span><span class="o">:</span>
    <span class="cm">/*static function*/</span>
    <span class="cm">/*rotate*/</span>
    <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="n">rotateLeft</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">);</span>

    <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">rotateRight</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">);</span>

    <span class="cm">/*insert&amp;remove*/</span>
    <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">insert</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="kt">int</span> <span class="n">val</span><span class="p">,</span> <span class="kt">int</span> <span class="o">&amp;</span><span class="n">size</span><span class="p">);</span>

    <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">remove</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="kt">int</span> <span class="n">val</span><span class="p">,</span> <span class="kt">int</span> <span class="o">&amp;</span><span class="n">size</span><span class="p">);</span>

    <span class="cm">/*query rank&amp;value*/</span>
    <span class="k">static</span> <span class="kt">int</span> <span class="nf">getLength</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">);</span>

    <span class="k">static</span> <span class="kt">int</span> <span class="nf">queryRank</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="kt">int</span> <span class="n">val</span><span class="p">);</span><span class="c1">//快速查询val的排名
</span><span class="c1"></span>    <span class="k">static</span> <span class="kt">int</span> <span class="nf">queryValue</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="kt">int</span> <span class="n">rank</span><span class="p">);</span><span class="c1">//快速查询排名为rank的数
</span><span class="c1"></span>    <span class="cm">/*query pre&amp;next*/</span>
    <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">queryPre</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="kt">int</span> <span class="n">val</span><span class="p">);</span>

    <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">queryNext</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="kt">int</span> <span class="n">val</span><span class="p">);</span>

    <span class="k">static</span> <span class="kt">void</span> <span class="nf">inorder_print</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">);</span>

    <span class="k">static</span> <span class="kt">void</span> <span class="nf">destroy</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">);</span>

<span class="k">public</span><span class="o">:</span>
    <span class="cm">/*public function*/</span>
    <span class="cm">/*insert&amp;remove*/</span>
    <span class="kt">void</span> <span class="n">insert</span><span class="p">(</span><span class="kt">int</span> <span class="n">val</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">head</span> <span class="o">=</span> <span class="n">insert</span><span class="p">(</span><span class="n">head</span><span class="p">,</span> <span class="n">val</span><span class="p">,</span> <span class="n">length</span><span class="p">);</span>
    <span class="p">}</span>

    <span class="kt">void</span> <span class="nf">remove</span><span class="p">(</span><span class="kt">int</span> <span class="n">val</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">head</span> <span class="o">=</span> <span class="n">remove</span><span class="p">(</span><span class="n">head</span><span class="p">,</span> <span class="n">val</span><span class="p">,</span> <span class="n">length</span><span class="p">);</span>
    <span class="p">}</span>

    <span class="kt">int</span> <span class="nf">size</span><span class="p">()</span> <span class="p">{</span>
        <span class="k">return</span> <span class="n">length</span><span class="p">;</span>
    <span class="p">}</span>

    <span class="kt">bool</span> <span class="nf">isEmpty</span><span class="p">()</span> <span class="p">{</span>
        <span class="k">return</span> <span class="n">length</span> <span class="o">==</span> <span class="mi">0</span><span class="p">;</span>
    <span class="p">}</span>

    <span class="cm">/*query rank&amp;value*/</span>
    <span class="kt">int</span> <span class="nf">queryRank</span><span class="p">(</span><span class="kt">int</span> <span class="n">val</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">return</span> <span class="n">queryRank</span><span class="p">(</span><span class="n">head</span><span class="p">,</span> <span class="n">val</span><span class="p">);</span>
    <span class="p">}</span>

    <span class="kt">int</span> <span class="nf">queryValue</span><span class="p">(</span><span class="kt">int</span> <span class="n">rank</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">return</span> <span class="n">queryValue</span><span class="p">(</span><span class="n">head</span><span class="p">,</span> <span class="n">rank</span><span class="p">);</span>
    <span class="p">}</span>

    <span class="kt">void</span> <span class="nf">inorder_print</span><span class="p">()</span> <span class="p">{</span>
        <span class="n">inorder_print</span><span class="p">(</span><span class="n">head</span><span class="p">);</span>
    <span class="p">}</span>

    <span class="cm">/*begin&amp;end*/</span>
    <span class="n">iterator</span> <span class="nf">begin</span><span class="p">()</span> <span class="p">{</span>
        <span class="n">node</span> <span class="o">*</span><span class="n">t</span> <span class="o">=</span> <span class="n">head</span><span class="p">;</span>
        <span class="k">while</span> <span class="p">(</span><span class="n">t</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">!=</span> <span class="k">nullptr</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">t</span> <span class="o">=</span> <span class="n">t</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="k">return</span> <span class="n">iterator</span><span class="p">(</span><span class="n">head</span><span class="p">,</span> <span class="n">t</span><span class="p">);</span>
    <span class="p">}</span>

    <span class="n">iterator</span> <span class="nf">end</span><span class="p">()</span> <span class="p">{</span>
        <span class="k">return</span> <span class="n">iterator</span><span class="p">(</span><span class="n">head</span><span class="p">,</span> <span class="k">nullptr</span><span class="p">);</span>
    <span class="p">}</span>
<span class="p">};</span>
</code></pre></div><h3 id="3-左旋和右旋">3. 左旋和右旋</h3>
<blockquote>
<p>具体可以看我之前AVL树对左旋右旋的描述,这里只开发源码查看，<a href="https://blog.csdn.net/m0_50945504/article/details/120725019" target="_blank" rel="noopener noreffer">文章链接</a></p>
</blockquote>
<p><strong>左旋：</strong></p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="n">node</span> <span class="o">*</span><span class="n">Treap</span><span class="o">::</span><span class="n">rotateLeft</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span>
    <span class="n">node</span> <span class="o">*</span><span class="n">son</span> <span class="o">=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">;</span>
    <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">=</span> <span class="n">son</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">;</span>
    <span class="n">son</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">=</span> <span class="n">root</span><span class="p">;</span>
    <span class="n">root</span><span class="o">-&gt;</span><span class="n">update</span><span class="p">();</span><span class="c1">//记得先更新底下的情况
</span><span class="c1"></span>    <span class="n">son</span><span class="o">-&gt;</span><span class="n">update</span><span class="p">();</span>
    <span class="k">return</span> <span class="n">son</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div><p><strong>右旋：</strong></p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="n">node</span> <span class="o">*</span><span class="n">Treap</span><span class="o">::</span><span class="n">rotateRight</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span>
    <span class="n">node</span> <span class="o">*</span><span class="n">son</span> <span class="o">=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">;</span>
    <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">=</span> <span class="n">son</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">;</span>
    <span class="n">son</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">=</span> <span class="n">root</span><span class="p">;</span>
    <span class="n">root</span><span class="o">-&gt;</span><span class="n">update</span><span class="p">();</span>
    <span class="n">son</span><span class="o">-&gt;</span><span class="n">update</span><span class="p">();</span>
    <span class="k">return</span> <span class="n">son</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div><h3 id="4-插入和删除">4. 插入和删除</h3>
<p><strong>插入：</strong></p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="n">node</span> <span class="o">*</span><span class="n">Treap</span><span class="o">::</span><span class="n">insert</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="kt">int</span> <span class="n">val</span><span class="p">,</span> <span class="kt">int</span> <span class="o">&amp;</span><span class="n">size</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">root</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span> <span class="p">{</span>
        <span class="o">++</span><span class="n">size</span><span class="p">;</span>
        <span class="k">return</span> <span class="k">new</span> <span class="nf">node</span><span class="p">(</span><span class="n">val</span><span class="p">);</span>
    <span class="p">}</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">==</span> <span class="n">val</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">root</span><span class="o">-&gt;</span><span class="n">cnt</span><span class="o">++</span><span class="p">;</span>
        <span class="n">size</span><span class="o">++</span><span class="p">;</span>
    <span class="p">}</span> <span class="k">else</span> <span class="nf">if</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">&gt;</span> <span class="n">val</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">=</span> <span class="n">insert</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">,</span> <span class="n">val</span><span class="p">,</span> <span class="n">size</span><span class="p">);</span>
        <span class="c1">//根据优先级判断是否右旋，因为只可能在左边增加长度，通过维持优先级的大根堆
</span><span class="c1"></span>        <span class="k">if</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">priority</span> <span class="o">&lt;</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="o">-&gt;</span><span class="n">priority</span><span class="p">)</span> <span class="n">root</span> <span class="o">=</span> <span class="n">rotateRight</span><span class="p">(</span><span class="n">root</span><span class="p">);</span>
    <span class="p">}</span> <span class="k">else</span> <span class="nf">if</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">&lt;</span> <span class="n">val</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">=</span> <span class="n">insert</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">,</span> <span class="n">val</span><span class="p">,</span> <span class="n">size</span><span class="p">);</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">priority</span> <span class="o">&lt;</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="o">-&gt;</span><span class="n">priority</span><span class="p">)</span> <span class="n">root</span> <span class="o">=</span> <span class="n">rotateLeft</span><span class="p">(</span><span class="n">root</span><span class="p">);</span>
    <span class="p">}</span>
    <span class="n">root</span><span class="o">-&gt;</span><span class="n">update</span><span class="p">();</span><span class="c1">//注意更新长度信息
</span><span class="c1"></span>    <span class="k">return</span> <span class="n">root</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div><p><strong>删除：</strong></p>
<blockquote>
<p>删除这里还是详解一下：</p>
</blockquote>
<p>找到要删除的目标节点后，我们根据让树旋转使得优先级较大的孩子替换掉父亲（目标节点）。然后继续追杀父亲结点，直到该结点被逼到叶子结点，删除即可。</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="n">node</span> <span class="o">*</span><span class="n">Treap</span><span class="o">::</span><span class="n">remove</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="kt">int</span> <span class="n">val</span><span class="p">,</span> <span class="kt">int</span> <span class="o">&amp;</span><span class="n">size</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">root</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span><span class="k">return</span> <span class="k">nullptr</span><span class="p">;</span><span class="c1">//没找到
</span><span class="c1"></span>    <span class="k">if</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">==</span> <span class="n">val</span><span class="p">)</span> <span class="p">{</span>
        <span class="c1">//含有多个相同值，直接操作cnt即可
</span><span class="c1"></span>        <span class="k">if</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">cnt</span> <span class="o">&gt;</span> <span class="mi">1</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">root</span><span class="o">-&gt;</span><span class="n">cnt</span><span class="o">--</span><span class="p">;</span>
            <span class="o">--</span><span class="n">size</span><span class="p">;</span>
        <span class="p">}</span>
            <span class="c1">//分为两类情况：叶子结点情况和非叶子结点情况
</span><span class="c1"></span>        <span class="k">else</span> <span class="nf">if</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">!=</span> <span class="k">nullptr</span> <span class="o">||</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">!=</span> <span class="k">nullptr</span><span class="p">)</span> <span class="p">{</span>
            <span class="c1">//只有左子树或者左子树优先级大于右子树情况
</span><span class="c1"></span>            <span class="k">if</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">==</span> <span class="k">nullptr</span> <span class="o">||</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">!=</span> <span class="k">nullptr</span> <span class="o">&amp;&amp;</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="o">-&gt;</span><span class="n">priority</span> <span class="o">&gt;</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="o">-&gt;</span><span class="n">priority</span><span class="p">)</span> <span class="p">{</span>
                <span class="n">root</span> <span class="o">=</span> <span class="n">rotateRight</span><span class="p">(</span><span class="n">root</span><span class="p">);</span><span class="c1">//右旋后继续追杀
</span><span class="c1"></span>                <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">=</span> <span class="n">remove</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">,</span> <span class="n">val</span><span class="p">,</span> <span class="n">size</span><span class="p">);</span>
            <span class="p">}</span> <span class="k">else</span> <span class="p">{</span><span class="c1">//只有右子树或者右子树优先级大于左子树的情况
</span><span class="c1"></span>                <span class="n">root</span> <span class="o">=</span> <span class="n">rotateLeft</span><span class="p">(</span><span class="n">root</span><span class="p">);</span><span class="c1">//左旋后继续追杀
</span><span class="c1"></span>                <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">=</span> <span class="n">remove</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">,</span> <span class="n">val</span><span class="p">,</span> <span class="n">size</span><span class="p">);</span>
            <span class="p">}</span>
        <span class="p">}</span> <span class="k">else</span> <span class="p">{</span><span class="c1">//叶子结点情况，直接删除，然后把
</span><span class="c1"></span>            <span class="k">delete</span> <span class="n">root</span><span class="p">;</span>
            <span class="n">root</span> <span class="o">=</span> <span class="k">nullptr</span><span class="p">;</span>
            <span class="o">--</span><span class="n">size</span><span class="p">;</span>
        <span class="p">}</span>
    <span class="p">}</span> <span class="k">else</span> <span class="nf">if</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">&gt;</span> <span class="n">val</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">=</span> <span class="n">remove</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">,</span> <span class="n">val</span><span class="p">,</span> <span class="n">size</span><span class="p">);</span>
    <span class="p">}</span> <span class="k">else</span> <span class="nf">if</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">&lt;</span> <span class="n">val</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">=</span> <span class="n">remove</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">,</span> <span class="n">val</span><span class="p">,</span> <span class="n">size</span><span class="p">);</span>
    <span class="p">}</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">root</span><span class="p">)</span>
        <span class="n">root</span><span class="o">-&gt;</span><span class="n">update</span><span class="p">();</span>
    <span class="k">return</span> <span class="n">root</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div><h3 id="5-查询排名">5. 查询排名</h3>
<blockquote>
<p>原理：由于是排序二叉树，而且记录了树的结点个数，所以我们根据左边个数（小于当前结点的个数），如果我们的值小于当前结点的值，则小于它的个数范围肯定是在当前结点的左边，直接迁移到左孩子即可，如果大于当前结点，则当前结点的左边大小+它自身也是无法满足要查询的值的排名，rank加上该值后root继续右移。如果出现找到该元素的情况，则直接返回rank+左边长度。如果其中不存在，则最后得出的rank肯定是需要+1的。</p>
</blockquote>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="kr">inline</span> <span class="kt">int</span> <span class="n">Treap</span><span class="o">::</span><span class="n">getLength</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">root</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span>
        <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
    <span class="k">return</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">length</span><span class="p">;</span>
<span class="p">}</span>

<span class="kt">int</span> <span class="n">Treap</span><span class="o">::</span><span class="n">queryRank</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="kt">int</span> <span class="n">val</span><span class="p">)</span> <span class="p">{</span><span class="c1">//相当于查询有多少个数小于等于val
</span><span class="c1"></span>    <span class="kt">int</span> <span class="n">rank</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
    <span class="k">while</span> <span class="p">(</span><span class="n">root</span> <span class="o">!=</span> <span class="k">nullptr</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">==</span> <span class="n">val</span><span class="p">)</span><span class="k">return</span> <span class="n">rank</span> <span class="o">+</span> <span class="n">getLength</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">)</span> <span class="o">+</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">cnt</span><span class="p">;</span>
        <span class="k">else</span> <span class="nf">if</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">&gt;</span> <span class="n">val</span><span class="p">)</span><span class="n">root</span> <span class="o">=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">;</span>
        <span class="k">else</span> <span class="n">rank</span> <span class="o">+=</span> <span class="n">getLength</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">)</span> <span class="o">+</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">cnt</span><span class="p">,</span> <span class="n">root</span> <span class="o">=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="n">rank</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span><span class="c1">//如果未找到，则在原来的基础上+1
</span><span class="c1"></span><span class="p">}</span>
</code></pre></div><h3 id="6-按排名查询值">6. 按排名查询值</h3>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="kr">inline</span> <span class="kt">int</span> <span class="n">Treap</span><span class="o">::</span><span class="n">getLength</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">root</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span>
        <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
    <span class="k">return</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">length</span><span class="p">;</span>
<span class="p">}</span>
<span class="kt">int</span> <span class="n">Treap</span><span class="o">::</span><span class="n">queryValue</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="kt">int</span> <span class="n">rank</span><span class="p">)</span> <span class="p">{</span><span class="c1">//相当于得到第k大的数：支持重复元素是最骚的！！！
</span><span class="c1"></span>    <span class="k">while</span> <span class="p">(</span><span class="n">root</span> <span class="o">!=</span> <span class="k">nullptr</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">getLength</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">)</span> <span class="o">+</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">cnt</span> <span class="o">&gt;</span> <span class="n">rank</span><span class="p">)</span> <span class="p">{</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">getLength</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">)</span> <span class="o">+</span> <span class="mi">1</span> <span class="o">&gt;</span> <span class="n">rank</span><span class="p">)</span>
                <span class="n">root</span> <span class="o">=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">;</span>
            <span class="k">else</span>
                <span class="k">return</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">;</span>
        <span class="p">}</span> <span class="k">else</span> <span class="nf">if</span> <span class="p">(</span><span class="n">getLength</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">)</span> <span class="o">+</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">cnt</span> <span class="o">&lt;</span> <span class="n">rank</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">rank</span> <span class="o">-=</span> <span class="n">getLength</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">)</span> <span class="o">+</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">cnt</span><span class="p">;</span>
            <span class="n">root</span> <span class="o">=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">;</span>
        <span class="p">}</span> <span class="k">else</span> <span class="p">{</span><span class="c1">//rank与左子树的大小相等的情况
</span><span class="c1"></span>            <span class="k">return</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">;</span>
        <span class="p">}</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div><h3 id="7-查询前驱后继">7. 查询前驱后继</h3>
<p><strong>前驱：</strong></p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="n">node</span> <span class="o">*</span><span class="n">Treap</span><span class="o">::</span><span class="n">queryPre</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="kt">int</span> <span class="n">val</span><span class="p">)</span> <span class="p">{</span><span class="c1">//一样的道理：如果有左子树，就是左子树中最大的结点，如果没有则是最接近该结点的父节点(应在它的右侧
</span><span class="c1"></span>    <span class="n">node</span> <span class="o">*</span><span class="n">res</span> <span class="o">=</span> <span class="k">nullptr</span><span class="p">;</span>
    <span class="k">while</span> <span class="p">(</span><span class="n">root</span> <span class="o">!=</span> <span class="k">nullptr</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">&lt;</span> <span class="n">val</span><span class="p">)</span><span class="n">res</span> <span class="o">=</span> <span class="n">root</span><span class="p">,</span> <span class="n">root</span> <span class="o">=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">;</span>
        <span class="k">else</span> <span class="n">root</span> <span class="o">=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="n">res</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div><p><strong>后继：</strong></p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="n">node</span> <span class="o">*</span><span class="n">Treap</span><span class="o">::</span><span class="n">queryNext</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="kt">int</span> <span class="n">val</span><span class="p">)</span> <span class="p">{</span><span class="c1">//寻找后继
</span><span class="c1"></span>    <span class="n">node</span> <span class="o">*</span><span class="n">res</span> <span class="o">=</span> <span class="k">nullptr</span><span class="p">;</span>
    <span class="k">while</span> <span class="p">(</span><span class="n">root</span> <span class="o">!=</span> <span class="k">nullptr</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">&gt;</span> <span class="n">val</span><span class="p">)</span><span class="n">res</span> <span class="o">=</span> <span class="n">root</span><span class="p">,</span> <span class="n">root</span> <span class="o">=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">;</span>
        <span class="k">else</span> <span class="n">root</span> <span class="o">=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="n">res</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div><h3 id="8-销毁treap">8. 销毁Treap</h3>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="kt">void</span> <span class="n">Treap</span><span class="o">::</span><span class="n">destroy</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">root</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span>
        <span class="k">return</span><span class="p">;</span>
    <span class="n">destroy</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">);</span>
    <span class="n">destroy</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">);</span>
    <span class="k">delete</span> <span class="n">root</span><span class="p">;</span>
    <span class="n">root</span> <span class="o">=</span> <span class="k">nullptr</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div><h3 id="9-迭代器的设计">9. 迭代器的设计</h3>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">public</span><span class="o">:</span><span class="c1">//内部类设计迭代器
</span><span class="c1"></span>    <span class="k">class</span> <span class="nc">iterator</span> <span class="p">{</span>
        <span class="n">node</span> <span class="o">*</span><span class="n">head</span><span class="p">;</span>
        <span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">;</span>
    <span class="k">public</span><span class="o">:</span>
        <span class="cm">/*迭代器部分*/</span>
        <span class="n">iterator</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">head</span><span class="p">,</span> <span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="o">:</span> <span class="n">head</span><span class="p">(</span><span class="n">head</span><span class="p">),</span> <span class="n">root</span><span class="p">(</span><span class="n">root</span><span class="p">)</span> <span class="p">{}</span>

        <span class="n">iterator</span> <span class="o">&amp;</span><span class="k">operator</span><span class="o">++</span><span class="p">()</span> <span class="p">{</span>
            <span class="n">root</span> <span class="o">=</span> <span class="n">queryNext</span><span class="p">(</span><span class="n">head</span><span class="p">,</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">);</span>
            <span class="k">return</span> <span class="o">*</span><span class="k">this</span><span class="p">;</span>
        <span class="p">}</span>

        <span class="n">iterator</span> <span class="k">operator</span><span class="o">++</span><span class="p">(</span><span class="kt">int</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">iterator</span> <span class="n">t</span> <span class="o">=</span> <span class="o">*</span><span class="k">this</span><span class="p">;</span>
            <span class="n">root</span> <span class="o">=</span> <span class="n">queryNext</span><span class="p">(</span><span class="n">head</span><span class="p">,</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">);</span>
            <span class="k">return</span> <span class="n">t</span><span class="p">;</span>
        <span class="p">}</span>

        <span class="n">iterator</span> <span class="o">&amp;</span><span class="k">operator</span><span class="o">--</span><span class="p">()</span> <span class="p">{</span>
            <span class="n">root</span> <span class="o">=</span> <span class="n">queryPre</span><span class="p">(</span><span class="n">head</span><span class="p">,</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">);</span>
            <span class="k">return</span> <span class="o">*</span><span class="k">this</span><span class="p">;</span>
        <span class="p">}</span>

        <span class="n">iterator</span> <span class="k">operator</span><span class="o">--</span><span class="p">(</span><span class="kt">int</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">iterator</span> <span class="n">t</span> <span class="o">=</span> <span class="o">*</span><span class="k">this</span><span class="p">;</span>
            <span class="n">root</span> <span class="o">=</span> <span class="n">queryPre</span><span class="p">(</span><span class="n">head</span><span class="p">,</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">);</span>
            <span class="k">return</span> <span class="n">t</span><span class="p">;</span>
        <span class="p">}</span>

        <span class="kt">int</span> <span class="k">operator</span><span class="o">*</span><span class="p">()</span> <span class="p">{</span>
            <span class="k">return</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">;</span>
        <span class="p">}</span>

        <span class="kt">bool</span> <span class="k">operator</span><span class="o">!=</span><span class="p">(</span><span class="k">const</span> <span class="n">iterator</span> <span class="o">&amp;</span><span class="n">t</span><span class="p">)</span> <span class="p">{</span>
            <span class="k">return</span> <span class="n">t</span><span class="p">.</span><span class="n">root</span> <span class="o">!=</span> <span class="n">root</span><span class="p">;</span>
        <span class="p">}</span>
    <span class="p">};</span>
</code></pre></div><h2 id="完整源代码">完整源代码</h2>
<h3 id="treaph">Treap.h</h3>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="c1">//
</span><span class="c1">// Created by Alone on 2021/10/14.
</span><span class="c1">//
</span><span class="c1"></span>
<span class="cp">#ifndef MY_TINY_STL_TREAP_H
</span><span class="cp">#define MY_TINY_STL_TREAP_H
</span><span class="cp"></span>
<span class="cp">#include</span> <span class="cpf">&lt;cstdio&gt;</span><span class="cp">
</span><span class="cp">#include</span> <span class="cpf">&lt;cstdlib&gt;</span><span class="cp">
</span><span class="cp">#include</span> <span class="cpf">&lt;ctime&gt;</span><span class="cp">
</span><span class="cp"></span>
<span class="k">struct</span> <span class="nc">node</span> <span class="p">{</span>
    <span class="kt">int</span> <span class="n">val</span><span class="p">,</span> <span class="n">priority</span><span class="p">,</span> <span class="n">length</span><span class="p">,</span> <span class="n">cnt</span><span class="p">;</span>
    <span class="n">node</span> <span class="o">*</span><span class="n">lchild</span><span class="p">;</span>
    <span class="n">node</span> <span class="o">*</span><span class="n">rchild</span><span class="p">;</span>

    <span class="n">node</span><span class="p">()</span> <span class="o">:</span> <span class="n">val</span><span class="p">(</span><span class="mi">0</span><span class="p">),</span> <span class="n">length</span><span class="p">(</span><span class="mi">1</span><span class="p">),</span> <span class="n">cnt</span><span class="p">(</span><span class="mi">1</span><span class="p">),</span> <span class="n">lchild</span><span class="p">(</span><span class="k">nullptr</span><span class="p">),</span> <span class="n">rchild</span><span class="p">(</span><span class="k">nullptr</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">srand</span><span class="p">((</span><span class="kt">unsigned</span><span class="p">)</span> <span class="n">time</span><span class="p">(</span><span class="nb">NULL</span><span class="p">));</span><span class="c1">//记得重新设定种子
</span><span class="c1"></span>        <span class="n">priority</span> <span class="o">=</span> <span class="n">rand</span><span class="p">();</span>
    <span class="p">}</span>

    <span class="n">node</span><span class="p">(</span><span class="kt">int</span> <span class="n">val</span><span class="p">)</span> <span class="o">:</span> <span class="n">val</span><span class="p">(</span><span class="n">val</span><span class="p">),</span> <span class="n">length</span><span class="p">(</span><span class="mi">1</span><span class="p">),</span> <span class="n">cnt</span><span class="p">(</span><span class="mi">1</span><span class="p">),</span> <span class="n">lchild</span><span class="p">(</span><span class="k">nullptr</span><span class="p">),</span> <span class="n">rchild</span><span class="p">(</span><span class="k">nullptr</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">srand</span><span class="p">((</span><span class="kt">unsigned</span><span class="p">)</span> <span class="n">time</span><span class="p">(</span><span class="nb">NULL</span><span class="p">));</span>
        <span class="n">priority</span> <span class="o">=</span> <span class="n">rand</span><span class="p">();</span>
    <span class="p">}</span>

    <span class="kt">void</span> <span class="nf">update</span><span class="p">()</span> <span class="p">{</span>
        <span class="n">length</span> <span class="o">=</span> <span class="n">cnt</span><span class="p">;</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">lchild</span> <span class="o">!=</span> <span class="k">nullptr</span><span class="p">)</span><span class="n">length</span> <span class="o">+=</span> <span class="n">lchild</span><span class="o">-&gt;</span><span class="n">length</span><span class="p">;</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">rchild</span> <span class="o">!=</span> <span class="k">nullptr</span><span class="p">)</span><span class="n">length</span> <span class="o">+=</span> <span class="n">rchild</span><span class="o">-&gt;</span><span class="n">length</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">};</span>

<span class="k">class</span> <span class="nc">Treap</span> <span class="p">{</span>
    <span class="n">node</span> <span class="o">*</span><span class="n">head</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">length</span><span class="p">;</span>
<span class="k">public</span><span class="o">:</span>
    <span class="cm">/*construct&amp;destruct*/</span>
    <span class="n">Treap</span><span class="p">()</span> <span class="o">:</span> <span class="n">head</span><span class="p">(</span><span class="k">nullptr</span><span class="p">),</span> <span class="n">length</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span> <span class="p">{}</span>

    <span class="n">Treap</span><span class="p">(</span><span class="kt">int</span> <span class="n">val</span><span class="p">)</span> <span class="o">:</span> <span class="n">head</span><span class="p">(</span><span class="k">new</span> <span class="n">node</span><span class="p">(</span><span class="n">val</span><span class="p">)),</span> <span class="n">length</span><span class="p">(</span><span class="mi">1</span><span class="p">)</span> <span class="p">{}</span>
    <span class="o">~</span><span class="n">Treap</span><span class="p">(){</span>
        <span class="n">destroy</span><span class="p">(</span><span class="n">head</span><span class="p">);</span>
    <span class="p">}</span>

<span class="k">public</span><span class="o">:</span><span class="c1">//内部类设计迭代器
</span><span class="c1"></span>    <span class="k">class</span> <span class="nc">iterator</span> <span class="p">{</span>
        <span class="n">node</span> <span class="o">*</span><span class="n">head</span><span class="p">;</span>
        <span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">;</span>
    <span class="k">public</span><span class="o">:</span>
        <span class="cm">/*迭代器部分*/</span>
        <span class="n">iterator</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">head</span><span class="p">,</span> <span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="o">:</span> <span class="n">head</span><span class="p">(</span><span class="n">head</span><span class="p">),</span> <span class="n">root</span><span class="p">(</span><span class="n">root</span><span class="p">)</span> <span class="p">{}</span>

        <span class="n">iterator</span> <span class="o">&amp;</span><span class="k">operator</span><span class="o">++</span><span class="p">()</span> <span class="p">{</span>
            <span class="n">root</span> <span class="o">=</span> <span class="n">queryNext</span><span class="p">(</span><span class="n">head</span><span class="p">,</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">);</span>
            <span class="k">return</span> <span class="o">*</span><span class="k">this</span><span class="p">;</span>
        <span class="p">}</span>

        <span class="n">iterator</span> <span class="k">operator</span><span class="o">++</span><span class="p">(</span><span class="kt">int</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">iterator</span> <span class="n">t</span> <span class="o">=</span> <span class="o">*</span><span class="k">this</span><span class="p">;</span>
            <span class="n">root</span> <span class="o">=</span> <span class="n">queryNext</span><span class="p">(</span><span class="n">head</span><span class="p">,</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">);</span>
            <span class="k">return</span> <span class="n">t</span><span class="p">;</span>
        <span class="p">}</span>

        <span class="n">iterator</span> <span class="o">&amp;</span><span class="k">operator</span><span class="o">--</span><span class="p">()</span> <span class="p">{</span>
            <span class="n">root</span> <span class="o">=</span> <span class="n">queryPre</span><span class="p">(</span><span class="n">head</span><span class="p">,</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">);</span>
            <span class="k">return</span> <span class="o">*</span><span class="k">this</span><span class="p">;</span>
        <span class="p">}</span>

        <span class="n">iterator</span> <span class="k">operator</span><span class="o">--</span><span class="p">(</span><span class="kt">int</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">iterator</span> <span class="n">t</span> <span class="o">=</span> <span class="o">*</span><span class="k">this</span><span class="p">;</span>
            <span class="n">root</span> <span class="o">=</span> <span class="n">queryPre</span><span class="p">(</span><span class="n">head</span><span class="p">,</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">);</span>
            <span class="k">return</span> <span class="n">t</span><span class="p">;</span>
        <span class="p">}</span>

        <span class="kt">int</span> <span class="k">operator</span><span class="o">*</span><span class="p">()</span> <span class="p">{</span>
            <span class="k">return</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">;</span>
        <span class="p">}</span>

        <span class="kt">bool</span> <span class="k">operator</span><span class="o">!=</span><span class="p">(</span><span class="k">const</span> <span class="n">iterator</span> <span class="o">&amp;</span><span class="n">t</span><span class="p">)</span> <span class="p">{</span>
            <span class="k">return</span> <span class="n">t</span><span class="p">.</span><span class="n">root</span> <span class="o">!=</span> <span class="n">root</span><span class="p">;</span>
        <span class="p">}</span>
    <span class="p">};</span>

<span class="k">private</span><span class="o">:</span>
    <span class="cm">/*static function*/</span>
    <span class="cm">/*rotate*/</span>
    <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="n">rotateLeft</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">);</span>

    <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">rotateRight</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">);</span>

    <span class="cm">/*insert&amp;remove*/</span>
    <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">insert</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="kt">int</span> <span class="n">val</span><span class="p">,</span> <span class="kt">int</span> <span class="o">&amp;</span><span class="n">size</span><span class="p">);</span>

    <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">remove</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="kt">int</span> <span class="n">val</span><span class="p">,</span> <span class="kt">int</span> <span class="o">&amp;</span><span class="n">size</span><span class="p">);</span>

    <span class="cm">/*query rank&amp;value*/</span>
    <span class="k">static</span> <span class="kt">int</span> <span class="nf">getLength</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">);</span>

    <span class="k">static</span> <span class="kt">int</span> <span class="nf">queryRank</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="kt">int</span> <span class="n">val</span><span class="p">);</span><span class="c1">//快速查询val的排名
</span><span class="c1"></span>    <span class="k">static</span> <span class="kt">int</span> <span class="nf">queryValue</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="kt">int</span> <span class="n">rank</span><span class="p">);</span><span class="c1">//快速查询排名为rank的数
</span><span class="c1"></span>    <span class="cm">/*query pre&amp;next*/</span>
    <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">queryPre</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="kt">int</span> <span class="n">val</span><span class="p">);</span>

    <span class="k">static</span> <span class="n">node</span> <span class="o">*</span><span class="nf">queryNext</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="kt">int</span> <span class="n">val</span><span class="p">);</span>

    <span class="k">static</span> <span class="kt">void</span> <span class="nf">inorder_print</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">);</span>

    <span class="k">static</span> <span class="kt">void</span> <span class="nf">destroy</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">);</span>

<span class="k">public</span><span class="o">:</span>
    <span class="cm">/*public function*/</span>
    <span class="cm">/*insert&amp;remove*/</span>
    <span class="kt">void</span> <span class="n">insert</span><span class="p">(</span><span class="kt">int</span> <span class="n">val</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">head</span> <span class="o">=</span> <span class="n">insert</span><span class="p">(</span><span class="n">head</span><span class="p">,</span> <span class="n">val</span><span class="p">,</span> <span class="n">length</span><span class="p">);</span>
    <span class="p">}</span>

    <span class="kt">void</span> <span class="nf">remove</span><span class="p">(</span><span class="kt">int</span> <span class="n">val</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">head</span> <span class="o">=</span> <span class="n">remove</span><span class="p">(</span><span class="n">head</span><span class="p">,</span> <span class="n">val</span><span class="p">,</span> <span class="n">length</span><span class="p">);</span>
    <span class="p">}</span>

    <span class="kt">int</span> <span class="nf">size</span><span class="p">()</span> <span class="p">{</span>
        <span class="k">return</span> <span class="n">length</span><span class="p">;</span>
    <span class="p">}</span>

    <span class="kt">bool</span> <span class="nf">isEmpty</span><span class="p">()</span> <span class="p">{</span>
        <span class="k">return</span> <span class="n">length</span> <span class="o">==</span> <span class="mi">0</span><span class="p">;</span>
    <span class="p">}</span>

    <span class="cm">/*query rank&amp;value*/</span>
    <span class="kt">int</span> <span class="nf">queryRank</span><span class="p">(</span><span class="kt">int</span> <span class="n">val</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">return</span> <span class="n">queryRank</span><span class="p">(</span><span class="n">head</span><span class="p">,</span> <span class="n">val</span><span class="p">);</span>
    <span class="p">}</span>

    <span class="kt">int</span> <span class="nf">queryValue</span><span class="p">(</span><span class="kt">int</span> <span class="n">rank</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">return</span> <span class="n">queryValue</span><span class="p">(</span><span class="n">head</span><span class="p">,</span> <span class="n">rank</span><span class="p">);</span>
    <span class="p">}</span>

    <span class="kt">void</span> <span class="nf">inorder_print</span><span class="p">()</span> <span class="p">{</span>
        <span class="n">inorder_print</span><span class="p">(</span><span class="n">head</span><span class="p">);</span>
    <span class="p">}</span>

    <span class="cm">/*begin&amp;end*/</span>
    <span class="n">iterator</span> <span class="nf">begin</span><span class="p">()</span> <span class="p">{</span>
        <span class="n">node</span> <span class="o">*</span><span class="n">t</span> <span class="o">=</span> <span class="n">head</span><span class="p">;</span>
        <span class="k">while</span> <span class="p">(</span><span class="n">t</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">!=</span> <span class="k">nullptr</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">t</span> <span class="o">=</span> <span class="n">t</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="k">return</span> <span class="n">iterator</span><span class="p">(</span><span class="n">head</span><span class="p">,</span> <span class="n">t</span><span class="p">);</span>
    <span class="p">}</span>

    <span class="n">iterator</span> <span class="nf">end</span><span class="p">()</span> <span class="p">{</span>
        <span class="k">return</span> <span class="n">iterator</span><span class="p">(</span><span class="n">head</span><span class="p">,</span> <span class="k">nullptr</span><span class="p">);</span>
    <span class="p">}</span>
<span class="p">};</span>


<span class="cp">#endif </span><span class="c1">//MY_TINY_STL_TREAP_H
</span></code></pre></div><h3 id="treapcpp">Treap.cpp</h3>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="c1">//
</span><span class="c1">// Created by Alone on 2021/10/14.
</span><span class="c1">//
</span><span class="c1"></span>
<span class="cp">#include</span> <span class="cpf">&#34;Treap.h&#34;</span><span class="cp">
</span><span class="cp"></span>
<span class="n">node</span> <span class="o">*</span><span class="n">Treap</span><span class="o">::</span><span class="n">rotateLeft</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span>
    <span class="n">node</span> <span class="o">*</span><span class="n">son</span> <span class="o">=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">;</span>
    <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">=</span> <span class="n">son</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">;</span>
    <span class="n">son</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">=</span> <span class="n">root</span><span class="p">;</span>
    <span class="n">root</span><span class="o">-&gt;</span><span class="n">update</span><span class="p">();</span><span class="c1">//记得先更新底下的情况
</span><span class="c1"></span>    <span class="n">son</span><span class="o">-&gt;</span><span class="n">update</span><span class="p">();</span>
    <span class="k">return</span> <span class="n">son</span><span class="p">;</span>
<span class="p">}</span>

<span class="n">node</span> <span class="o">*</span><span class="n">Treap</span><span class="o">::</span><span class="n">rotateRight</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span>
    <span class="n">node</span> <span class="o">*</span><span class="n">son</span> <span class="o">=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">;</span>
    <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">=</span> <span class="n">son</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">;</span>
    <span class="n">son</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">=</span> <span class="n">root</span><span class="p">;</span>
    <span class="n">root</span><span class="o">-&gt;</span><span class="n">update</span><span class="p">();</span>
    <span class="n">son</span><span class="o">-&gt;</span><span class="n">update</span><span class="p">();</span>
    <span class="k">return</span> <span class="n">son</span><span class="p">;</span>
<span class="p">}</span>

<span class="n">node</span> <span class="o">*</span><span class="n">Treap</span><span class="o">::</span><span class="n">insert</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="kt">int</span> <span class="n">val</span><span class="p">,</span> <span class="kt">int</span> <span class="o">&amp;</span><span class="n">size</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">root</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span> <span class="p">{</span>
        <span class="o">++</span><span class="n">size</span><span class="p">;</span>
        <span class="k">return</span> <span class="k">new</span> <span class="nf">node</span><span class="p">(</span><span class="n">val</span><span class="p">);</span>
    <span class="p">}</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">==</span> <span class="n">val</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">root</span><span class="o">-&gt;</span><span class="n">cnt</span><span class="o">++</span><span class="p">;</span>
        <span class="n">size</span><span class="o">++</span><span class="p">;</span>
    <span class="p">}</span> <span class="k">else</span> <span class="nf">if</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">&gt;</span> <span class="n">val</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">=</span> <span class="n">insert</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">,</span> <span class="n">val</span><span class="p">,</span> <span class="n">size</span><span class="p">);</span>
        <span class="c1">//根据优先级判断是否右旋，因为只可能在左边增加长度，通过维持优先级的大根堆
</span><span class="c1"></span>        <span class="k">if</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">priority</span> <span class="o">&lt;</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="o">-&gt;</span><span class="n">priority</span><span class="p">)</span> <span class="n">root</span> <span class="o">=</span> <span class="n">rotateRight</span><span class="p">(</span><span class="n">root</span><span class="p">);</span>
    <span class="p">}</span> <span class="k">else</span> <span class="nf">if</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">&lt;</span> <span class="n">val</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">=</span> <span class="n">insert</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">,</span> <span class="n">val</span><span class="p">,</span> <span class="n">size</span><span class="p">);</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">priority</span> <span class="o">&lt;</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="o">-&gt;</span><span class="n">priority</span><span class="p">)</span> <span class="n">root</span> <span class="o">=</span> <span class="n">rotateLeft</span><span class="p">(</span><span class="n">root</span><span class="p">);</span>
    <span class="p">}</span>
    <span class="n">root</span><span class="o">-&gt;</span><span class="n">update</span><span class="p">();</span>
    <span class="k">return</span> <span class="n">root</span><span class="p">;</span>
<span class="p">}</span>

<span class="n">node</span> <span class="o">*</span><span class="n">Treap</span><span class="o">::</span><span class="n">remove</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="kt">int</span> <span class="n">val</span><span class="p">,</span> <span class="kt">int</span> <span class="o">&amp;</span><span class="n">size</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">root</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span><span class="k">return</span> <span class="k">nullptr</span><span class="p">;</span><span class="c1">//没找到
</span><span class="c1"></span>    <span class="k">if</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">==</span> <span class="n">val</span><span class="p">)</span> <span class="p">{</span>
        <span class="c1">//含有多个相同值，直接操作cnt即可
</span><span class="c1"></span>        <span class="k">if</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">cnt</span> <span class="o">&gt;</span> <span class="mi">1</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">root</span><span class="o">-&gt;</span><span class="n">cnt</span><span class="o">--</span><span class="p">;</span>
            <span class="o">--</span><span class="n">size</span><span class="p">;</span>
        <span class="p">}</span>
            <span class="c1">//分为两类情况：叶子结点情况和非叶子结点情况
</span><span class="c1"></span>        <span class="k">else</span> <span class="nf">if</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">!=</span> <span class="k">nullptr</span> <span class="o">||</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">!=</span> <span class="k">nullptr</span><span class="p">)</span> <span class="p">{</span>
            <span class="c1">//只有左子树或者左子树优先级大于右子树情况
</span><span class="c1"></span>            <span class="k">if</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">==</span> <span class="k">nullptr</span> <span class="o">||</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">!=</span> <span class="k">nullptr</span> <span class="o">&amp;&amp;</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="o">-&gt;</span><span class="n">priority</span> <span class="o">&gt;</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="o">-&gt;</span><span class="n">priority</span><span class="p">)</span> <span class="p">{</span>
                <span class="n">root</span> <span class="o">=</span> <span class="n">rotateRight</span><span class="p">(</span><span class="n">root</span><span class="p">);</span><span class="c1">//右旋后继续追杀
</span><span class="c1"></span>                <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">=</span> <span class="n">remove</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">,</span> <span class="n">val</span><span class="p">,</span> <span class="n">size</span><span class="p">);</span>
            <span class="p">}</span> <span class="k">else</span> <span class="p">{</span><span class="c1">//只有右子树或者右子树优先级大于左子树的情况
</span><span class="c1"></span>                <span class="n">root</span> <span class="o">=</span> <span class="n">rotateLeft</span><span class="p">(</span><span class="n">root</span><span class="p">);</span><span class="c1">//左旋后继续追杀
</span><span class="c1"></span>                <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">=</span> <span class="n">remove</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">,</span> <span class="n">val</span><span class="p">,</span> <span class="n">size</span><span class="p">);</span>
            <span class="p">}</span>
        <span class="p">}</span> <span class="k">else</span> <span class="p">{</span><span class="c1">//叶子结点情况，直接删除，然后把
</span><span class="c1"></span>            <span class="k">delete</span> <span class="n">root</span><span class="p">;</span>
            <span class="n">root</span> <span class="o">=</span> <span class="k">nullptr</span><span class="p">;</span>
            <span class="o">--</span><span class="n">size</span><span class="p">;</span>
        <span class="p">}</span>
    <span class="p">}</span> <span class="k">else</span> <span class="nf">if</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">&gt;</span> <span class="n">val</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">=</span> <span class="n">remove</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">,</span> <span class="n">val</span><span class="p">,</span> <span class="n">size</span><span class="p">);</span>
    <span class="p">}</span> <span class="k">else</span> <span class="nf">if</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">&lt;</span> <span class="n">val</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">=</span> <span class="n">remove</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">,</span> <span class="n">val</span><span class="p">,</span> <span class="n">size</span><span class="p">);</span>
    <span class="p">}</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">root</span><span class="p">)</span>
        <span class="n">root</span><span class="o">-&gt;</span><span class="n">update</span><span class="p">();</span>
    <span class="k">return</span> <span class="n">root</span><span class="p">;</span>
<span class="p">}</span>

<span class="kt">int</span> <span class="n">Treap</span><span class="o">::</span><span class="n">queryRank</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="kt">int</span> <span class="n">val</span><span class="p">)</span> <span class="p">{</span><span class="c1">//相当于查询有多少个数小于等于val
</span><span class="c1"></span>    <span class="kt">int</span> <span class="n">rank</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
    <span class="k">while</span> <span class="p">(</span><span class="n">root</span> <span class="o">!=</span> <span class="k">nullptr</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">==</span> <span class="n">val</span><span class="p">)</span><span class="k">return</span> <span class="n">rank</span> <span class="o">+</span> <span class="n">getLength</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">)</span> <span class="o">+</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">cnt</span><span class="p">;</span>
        <span class="k">else</span> <span class="nf">if</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">&gt;</span> <span class="n">val</span><span class="p">)</span><span class="n">root</span> <span class="o">=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">;</span>
        <span class="k">else</span> <span class="n">rank</span> <span class="o">+=</span> <span class="n">getLength</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">)</span> <span class="o">+</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">cnt</span><span class="p">,</span> <span class="n">root</span> <span class="o">=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="n">rank</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span><span class="c1">//如果未找到，则在原来的基础上+1
</span><span class="c1"></span><span class="p">}</span>

<span class="kt">int</span> <span class="n">Treap</span><span class="o">::</span><span class="n">queryValue</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="kt">int</span> <span class="n">rank</span><span class="p">)</span> <span class="p">{</span><span class="c1">//相当于得到第k大的数：支持重复元素是最骚的！！！
</span><span class="c1"></span>    <span class="k">while</span> <span class="p">(</span><span class="n">root</span> <span class="o">!=</span> <span class="k">nullptr</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">getLength</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">)</span> <span class="o">+</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">cnt</span> <span class="o">&gt;</span> <span class="n">rank</span><span class="p">)</span> <span class="p">{</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">getLength</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">)</span> <span class="o">+</span> <span class="mi">1</span> <span class="o">&gt;</span> <span class="n">rank</span><span class="p">)</span>
                <span class="n">root</span> <span class="o">=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">;</span>
            <span class="k">else</span>
                <span class="k">return</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">;</span>
        <span class="p">}</span> <span class="k">else</span> <span class="nf">if</span> <span class="p">(</span><span class="n">getLength</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">)</span> <span class="o">+</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">cnt</span> <span class="o">&lt;</span> <span class="n">rank</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">rank</span> <span class="o">-=</span> <span class="n">getLength</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">)</span> <span class="o">+</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">cnt</span><span class="p">;</span>
            <span class="n">root</span> <span class="o">=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">;</span>
        <span class="p">}</span> <span class="k">else</span> <span class="p">{</span><span class="c1">//rank与左子树的大小相等的情况
</span><span class="c1"></span>            <span class="k">return</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">;</span>
        <span class="p">}</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
<span class="p">}</span>

<span class="n">node</span> <span class="o">*</span><span class="n">Treap</span><span class="o">::</span><span class="n">queryPre</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="kt">int</span> <span class="n">val</span><span class="p">)</span> <span class="p">{</span><span class="c1">//一样的道理：如果有左子树，就是左子树中最大的结点，如果没有则是最接近该结点的父节点(应在它的右侧
</span><span class="c1"></span>    <span class="n">node</span> <span class="o">*</span><span class="n">res</span> <span class="o">=</span> <span class="k">nullptr</span><span class="p">;</span>
    <span class="k">while</span> <span class="p">(</span><span class="n">root</span> <span class="o">!=</span> <span class="k">nullptr</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">&lt;</span> <span class="n">val</span><span class="p">)</span><span class="n">res</span> <span class="o">=</span> <span class="n">root</span><span class="p">,</span> <span class="n">root</span> <span class="o">=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">;</span>
        <span class="k">else</span> <span class="n">root</span> <span class="o">=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="n">res</span><span class="p">;</span>
<span class="p">}</span>

<span class="n">node</span> <span class="o">*</span><span class="n">Treap</span><span class="o">::</span><span class="n">queryNext</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">,</span> <span class="kt">int</span> <span class="n">val</span><span class="p">)</span> <span class="p">{</span><span class="c1">//寻找后继
</span><span class="c1"></span>    <span class="n">node</span> <span class="o">*</span><span class="n">res</span> <span class="o">=</span> <span class="k">nullptr</span><span class="p">;</span>
    <span class="k">while</span> <span class="p">(</span><span class="n">root</span> <span class="o">!=</span> <span class="k">nullptr</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">&gt;</span> <span class="n">val</span><span class="p">)</span><span class="n">res</span> <span class="o">=</span> <span class="n">root</span><span class="p">,</span> <span class="n">root</span> <span class="o">=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">;</span>
        <span class="k">else</span> <span class="n">root</span> <span class="o">=</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="n">res</span><span class="p">;</span>
<span class="p">}</span>

<span class="kt">void</span> <span class="n">Treap</span><span class="o">::</span><span class="n">inorder_print</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">root</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span>
        <span class="k">return</span><span class="p">;</span>
    <span class="n">inorder_print</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">);</span>
    <span class="n">printf</span><span class="p">(</span><span class="s">&#34;%d &#34;</span><span class="p">,</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">);</span>
    <span class="n">inorder_print</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">);</span>
<span class="p">}</span>

<span class="kt">void</span> <span class="n">Treap</span><span class="o">::</span><span class="n">destroy</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">root</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span>
        <span class="k">return</span><span class="p">;</span>
    <span class="n">destroy</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">);</span>
    <span class="n">destroy</span><span class="p">(</span><span class="n">root</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">);</span>
    <span class="k">delete</span> <span class="n">root</span><span class="p">;</span>
    <span class="n">root</span> <span class="o">=</span> <span class="k">nullptr</span><span class="p">;</span>
<span class="p">}</span>

<span class="kr">inline</span> <span class="kt">int</span> <span class="n">Treap</span><span class="o">::</span><span class="n">getLength</span><span class="p">(</span><span class="n">node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">root</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span>
        <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
    <span class="k">return</span> <span class="n">root</span><span class="o">-&gt;</span><span class="n">length</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div><h2 id="测试">测试</h2>
<h3 id="avl-vs-treap-vs-普通bst">AVL vs Treap vs 普通BST</h3>
<p><strong>测试数据量：1000w</strong>
直接来结论：
AVL极端情况下(插入的数据有序)，完爆所有平衡树。
Treap随机情况的插入表示不错！大部分时间可以和AVL持平。
BST别想了，这个1000w数据只有随机情况能用几分钟过，如果极端情况直接程序运行出错！</p>
<p><strong>整体小结：</strong></p>
<ul>
<li>第一轮：insert操作</li>
</ul>
<ol>
<li>随机情况Treap(看运气，毕竟随机事件) <code>&gt;=&lt;</code> AVL<code>&gt;&gt;</code> BST</li>
<li>极端情况AVL <code>&gt;&gt;</code> Treap， BST直接暴毙</li>
</ol>
<ul>
<li>第二轮: remove操作&ndash;Treap被AVL吊打，BST就别提了</li>
</ul>
<p>下面就没得继续展开的比较了，总结就是Treap相对好写一点，效率高不高看运气。</p>
<p>还有就是Treap在直接处理第K大的值具有优势，以及按排位查找具有优势。</p>
<p>优势：由于treap每个结点都含有它整个结点个数的记录，所以可以很快的查出值的排名和排名的值。</p>
</div><div class="post-footer" id="post-footer">
    <div class="post-info"><div class="post-info-tag"><span><a href="/tags/%E6%9D%A5%E8%87%AA%E4%B8%8A%E5%B8%9D%E7%9A%84%E9%AA%B0%E5%AD%90-treap%E6%A0%91%E5%A0%86%E8%AF%A6%E8%A7%A3/">来自上帝的骰子---Treap(树堆)详解</a>
                </span></div><div class="post-info-line"><div class="post-info-mod">
                <span>更新于 2022-02-16</span>
            </div><div class="post-info-mod"></div>
        </div><div class="post-info-share">
            <span><a href="javascript:void(0);" title="分享到 Twitter" data-sharer="twitter" data-url="https://acking-you.github.io/posts/%E6%9D%A5%E8%87%AA%E4%B8%8A%E5%B8%9D%E7%9A%84%E9%AA%B0%E5%AD%90-treap%E6%A0%91%E5%A0%86%E8%AF%A6%E8%A7%A3/" data-title="来自上帝的骰子---Treap(树堆)详解" data-hashtags="来自上帝的骰子---Treap(树堆)详解"><i class="fab fa-twitter fa-fw"></i></a><a href="javascript:void(0);" title="分享到 Facebook" data-sharer="facebook" data-url="https://acking-you.github.io/posts/%E6%9D%A5%E8%87%AA%E4%B8%8A%E5%B8%9D%E7%9A%84%E9%AA%B0%E5%AD%90-treap%E6%A0%91%E5%A0%86%E8%AF%A6%E8%A7%A3/" data-hashtag="来自上帝的骰子---Treap(树堆)详解"><i class="fab fa-facebook-square fa-fw"></i></a><a href="javascript:void(0);" title="分享到 WhatsApp" data-sharer="whatsapp" data-url="https://acking-you.github.io/posts/%E6%9D%A5%E8%87%AA%E4%B8%8A%E5%B8%9D%E7%9A%84%E9%AA%B0%E5%AD%90-treap%E6%A0%91%E5%A0%86%E8%AF%A6%E8%A7%A3/" data-title="来自上帝的骰子---Treap(树堆)详解" data-web><i class="fab fa-whatsapp fa-fw"></i></a><a href="javascript:void(0);" title="分享到 Line" data-sharer="line" data-url="https://acking-you.github.io/posts/%E6%9D%A5%E8%87%AA%E4%B8%8A%E5%B8%9D%E7%9A%84%E9%AA%B0%E5%AD%90-treap%E6%A0%91%E5%A0%86%E8%AF%A6%E8%A7%A3/" data-title="来自上帝的骰子---Treap(树堆)详解"><i class="fab fa-line fa-fw"></i></a><a href="javascript:void(0);" title="分享到 微博" data-sharer="weibo" data-url="https://acking-you.github.io/posts/%E6%9D%A5%E8%87%AA%E4%B8%8A%E5%B8%9D%E7%9A%84%E9%AA%B0%E5%AD%90-treap%E6%A0%91%E5%A0%86%E8%AF%A6%E8%A7%A3/" data-title="来自上帝的骰子---Treap(树堆)详解" data-image="https://img-blog.csdnimg.cn/img_convert/30474f138a1fd099890cfcb17099a60b.png#pic_center"><i class="fab fa-weibo fa-fw"></i></a><a href="javascript:void(0);" title="分享到 Myspace" data-sharer="myspace" data-url="https://acking-you.github.io/posts/%E6%9D%A5%E8%87%AA%E4%B8%8A%E5%B8%9D%E7%9A%84%E9%AA%B0%E5%AD%90-treap%E6%A0%91%E5%A0%86%E8%AF%A6%E8%A7%A3/" data-title="来自上帝的骰子---Treap(树堆)详解" data-description="来自上帝的骰子---Treap(树堆)详解"><i data-svg-src="/lib/simple-icons/icons/myspace.min.svg"></i></a><a href="javascript:void(0);" title="分享到 Blogger" data-sharer="blogger" data-url="https://acking-you.github.io/posts/%E6%9D%A5%E8%87%AA%E4%B8%8A%E5%B8%9D%E7%9A%84%E9%AA%B0%E5%AD%90-treap%E6%A0%91%E5%A0%86%E8%AF%A6%E8%A7%A3/" data-title="来自上帝的骰子---Treap(树堆)详解" data-description="来自上帝的骰子---Treap(树堆)详解"><i class="fab fa-blogger fa-fw"></i></a><a href="javascript:void(0);" title="分享到 Evernote" data-sharer="evernote" data-url="https://acking-you.github.io/posts/%E6%9D%A5%E8%87%AA%E4%B8%8A%E5%B8%9D%E7%9A%84%E9%AA%B0%E5%AD%90-treap%E6%A0%91%E5%A0%86%E8%AF%A6%E8%A7%A3/" data-title="来自上帝的骰子---Treap(树堆)详解"><i class="fab fa-evernote fa-fw"></i></a></span>
        </div></div><div class="post-nav"><a href="/posts/leetcode%E6%83%85%E4%BA%BA%E8%8A%82%E7%89%B9%E8%BE%91%E5%AF%BB%E6%89%BE%E5%8D%95%E8%BA%AB%E7%8B%97/" class="prev" rel="prev" title="leetcode情人节特辑——寻找单身狗"><i class="fas fa-angle-left fa-fw"></i>Previous Post</a>
            <a href="/posts/%E6%96%B0%E6%89%8B%E7%94%A8c&#43;&#43;%E5%86%99%E4%BA%86%E4%B8%AA%E6%B3%9B%E5%9E%8B%E5%A0%86%E6%95%88%E7%8E%87%E7%AB%9F%E6%AF%94stl%E7%9A%84%E6%9B%B4%E5%BF%AB/" class="next" rel="next" title="新手用C&#43;&#43;写了个泛型堆，效率竟比STL的更快？">Next Post<i class="fas fa-angle-right fa-fw"></i></a></div></div>
</div></article></div>
            </main>
            <footer class="footer"><div class="footer-container"><div class="footer-line">由 <a href="https://gohugo.io/" target="_blank" rel="noopener noreffer" title="Hugo 0.86.0">Hugo</a> 强力驱动 | 主题 - <a href="https://github.com/khusika/FeelIt" target="_blank" rel="noopener noreffer" title="FeelIt 1.0.1"><i class="fas fa-hand-holding-heart fa-fw"></i> FeelIt</a>
        </div><div class="footer-line" itemscope itemtype="http://schema.org/CreativeWork"><i class="far fa-copyright fa-fw"></i><span itemprop="copyrightYear">2023</span><span class="author" itemprop="copyrightHolder">&nbsp;<a href="/"></a></span></div>
</div>
</footer>
        </div>

        <div id="fixed-buttons"><a href="#" id="back-to-top" class="fixed-button" title="回到顶部">
                <i class="fas fa-chevron-up fa-fw"></i>
            </a></div><link rel="stylesheet" href="/lib/fontawesome-free/all.min.css"><link rel="stylesheet" href="/lib/animate/animate.min.css"><link rel="stylesheet" href="/lib/katex/katex.min.css"><link rel="stylesheet" href="/lib/katex/copy-tex.min.css"><script src="/lib/autocomplete/autocomplete.min.js"></script><script src="/lib/lunr/lunr.min.js"></script><script src="/lib/lunr/lunr.stemmer.support.min.js"></script><script src="/lib/lunr/lunr.zh.min.js"></script><script src="/lib/lazysizes/lazysizes.min.js"></script><script src="/lib/clipboard/clipboard.min.js"></script><script src="/lib/sharer/sharer.min.js"></script><script src="/lib/katex/katex.min.js"></script><script src="/lib/katex/auto-render.min.js"></script><script src="/lib/katex/copy-tex.min.js"></script><script src="/lib/katex/mhchem.min.js"></script><script>window.config={"code":{"copyTitle":"复制到剪贴板","maxShownLines":200},"comment":{},"math":{"delimiters":[{"display":true,"left":"$$","right":"$$"},{"display":true,"left":"\\[","right":"\\]"},{"display":false,"left":"$","right":"$"},{"display":false,"left":"\\(","right":"\\)"}],"strict":false},"search":{"highlightTag":"em","lunrIndexURL":"/index.json","lunrLanguageCode":"zh","lunrSegmentitURL":"/lib/lunr/lunr.segmentit.js","maxResultLength":100,"noResultsFound":"没有找到结果","snippetLength":50,"type":"lunr"}};</script><script src="/js/theme.min.js"></script></body></html>
